1. Field of the Invention
The invention relates to flash memories, and more particularly to block selection of flash memories.
2. Description of the Related Art
A flash memory comprises a plurality of blocks, and each of the blocks comprises a plurality of pages for data storage. When a controller wants to write data to a flash memory, the controller must select a target block from a plurality of blocks of the flash memory, and then after, the controller writes data to the target block. To manage data stored in the flash memory, the controller sometimes must select a target block from the blocks of the flash memory and then erase data stored in the target block. The target block from which data is erased is referred to as a victim block. The controller often needs to select a victim block from the flash memory.
Ordinarily, the controller selects a victim block according to scores of the blocks of the flash memory. The controller first evaluates scores of all blocks of the flash memory and then determines the victim block according to the evaluated scores. For example, the controller may determine a block with a maximum score to be a victim block. In another embodiment, the controller may determine a block with a minimum score to be a victim block. The controller therefore must determine an extreme value of the scores of the blocks before a victim block is determined.
Determination of an extreme value of scores of all blocks of a flash memory is not an easy task. First, the controller must maintain the scores of the blocks. In addition, the controller must determine the extreme value of the scores within a short time period. For example, according to the specification of the flash memory, when the host sends a write command to the controller, the controller must complete data writing to the flash memory in a time period of 200 ms. The controller therefore cannot expend a time period longer than 200 ms in determination of the extreme value of the scores of blocks of the flash memory.
The time expended by a controller to determine an extreme value of scores corresponds to the data structure for storing the scores of the blocks. Referring to FIG. 1A, a schematic diagram of scores stored in a queue 100 is shown. Scores S1˜SX of X blocks are sequentially stored in data storage units 101˜10X, and a controller must sequentially search the data storage units 101˜10X to determine an extreme value of the scores S1˜Sx. The controller therefore needs a long time period to determine the extreme value of the scores S1˜SX stored in the data storage units 101˜10X of the queue.
Referring to FIG. 1B, a schematic diagram of scores stored in a binary tree 120 is shown. A root node divides a binary tree 120 into a left subtree and a right subtree, wherein data stored in the nodes of the left subtree is smaller than data stored in the root node, but data stored in the nodes of the right subtree is greater than data stored in the root node. The extreme value is therefore stored in the node located at the lower-right corner of the binary tree 120. For example, the extreme value of the scores S1˜S12 is the score S12 stored in the lower-right node 132 of the binary tree 120. Although it is easier to find the extreme value of scores stored in a binary tree than that stored in a queue, the storage of scores into the binary tree also takes a long time period. For example, when a controller wants to store the score S12 into the binary tree 120, the score S12 must be sequentially compared with the scores stored in the nodes 121, 123, 125, 127, and 130, and a long time period is therefore needed.
Thus, a data structure is required to make a controller to record scores of blocks of a flash memory in the data structure in a short time period and to find an extreme value of scores stored in the data structure in a short time period.